This invention relates generally to joint encryption of data whereby two parties in a data processing system jointly generate a ciphertext. Methods are provided for joint ciphertext generation by devices of a data processing system, together with devices and computer programs for implementing such methods.
Public key encryption is an important cryptographic tool in substantially any security protocol which aims to protect data communicated in data processing systems. The encryption scheme relies on a pair of cryptographic keys, namely a secret key and a public key, which are associated with a particular party to communications in the system. A party's public key is available to all users of the scheme, whereas the secret key remains secret to that party. When used in a basic messaging process where a sender wishes to communicate with a recipient while keeping the message data secret from others, the sender can encrypt the secret data via a cryptographic encoding process using the recipient's public key. Security relies on the premise that the resulting ciphertext can only be decrypted to recover the original plaintext message, i.e. the secret data, using the corresponding secret key of the key-pair. Thus only the authorised recipient, in possession of this secret key, can decrypt the ciphertext to reveal the secret data.
Encryption schemes can also be used to encrypt data under the public key of a trusted entity, or “trusted third party” (TTP). A simple example of such an application is illustrated schematically in FIG. 1 of the accompanying drawings. In this scenario, a user, represented here by a user pc (personal computer) 1, requests access to an internet-based service provided by a verifier represented by verifier server 2. The verifier permits anonymous access to the service and sends the user a bill. The identity of user 1 is thus not disclosed to the verifier in this interaction, but the verifier must be able to hold the user to account in the event that his bill is not paid. To this end, before accessing the service, user 1 generates a ciphertext ct encrypting his secret identity data ID. The secret ID is encrypted under the public key pkTTP of a trusted entity represented in the figure by TTP server 3. Also encrypted in the ciphertext is certain “context” data associated with the transaction. The context data allows a particular transaction to be identified and may include data indicating date, time, verifier ID, etc. as required. The ciphertext ct is generated using a verifiable encryption process which allows a recipient of the ciphertext to verify that the ciphertext contains a valid user ID without learning the ID itself. The resulting ciphertext ct is sent to the verifier 2 who then permits the user access to the service. If the user does not subsequently pay his bill, the verifier can apply to TTP 3 to obtain the user's identity. To do this, verifier 2 sends the ciphertext ct to TTP 3, together with suitable proof of non-payment for the transaction associated with the context data in the ciphertext. If satisfied of the need to identify the user, the TTP 3 can decrypt the ciphertext ct using the secret TTP key skTTP corresponding to the public key pkTTP used for encryption. The decrypted user ID is returned to the verifier who can then pursue the user for payment.
Encrypting data under the public key of a trusted entity in systems like that of FIG. 1 provides a mechanism for balancing privacy and security in the system. The data encrypted under the trusted entity's public key is typically only used to investigate and punish a party who abuses the protocol in question. In this way, privacy can be afforded to “well-behaved” users whilst offering security to a verifying party that a misbehaving user can be held accountable for abuse. A particular example of such a system is detailed in our copending US Patent Application Publication No. US 2010/0142704 A1 and “Rethinking Accountable Privacy Supporting Services”, Camenisch et al., DIM'08, Fairfax, Va., USA, 31 Oct. 2008.
In practice, the level of security provided by an encryption scheme ultimately depends on the extent to which an attacker can deduce information from a ciphertext without knowledge of the secret key. The current de-facto standard security notion for encryption schemes is known as “security against chosen-ciphertext attack” (CCA). This is defined in terms of the probability with which a notional attacker, operating under specified constraints (which permit limited access to a decryption oracle for decryption of ciphertexts chosen by the attacker), can detect which of two messages (plaintexts) corresponds to a given ciphertext. CCA-security is now the standard requirement because schemes fulfilling weaker security notions, e.g. so-called “semantic security” (security against chosen-plaintext attack (CPA)) have been shown to be vulnerable to certain types of attack.
There are many efficient public-key encryption schemes, but most require use of some sort of hash function such as collision-resistant hash functions or cryptographic hash functions. In particular, CCA-secure encryption schemes are typically obtained from semantically secure encryption schemes by adding consistency checks that prevent an attacker from modifying an observed ciphertext without detection. The final ciphertext contains both the encrypted message, produced by encryption of the plaintext message, and a consistency check component which is generated from the encrypted message using a hash function. A recipient of the ciphertext can verify that the consistency component is correct for the encrypted message and hence that the encrypted message is valid (i.e. has been validly computed by the sender and so not modified by an attacker). While this provides the basis for CCA security, the use of hash or similar functions in these schemes prevents certain proofs being made about the resulting ciphertext. In particular, the use of such functions prevents one from efficiently proving certain relations between their input and output. Such proofs are, however, an important requirement in some advanced security protocols where high levels of privacy are required. Some protocols, for instance, require a user to prove knowledge of a ciphertext which is validly computed without revealing the ciphertext to the verifying party. Some protocols also require two parties jointly to generate an encryption of their respective messages without revealing those messages to each other. For example, two parties (such as the user and verifier in a scenario similar to FIG. 1) may wish jointly to generate an encryption of respective secret data under the public key of a TTP. This is a common requirement in privacy-protecting cryptographic protocols where the mechanism is used to balance privacy and security as discussed above. The need for CCA security poses a problem in such scenarios.
Examples of CCA-secure encryption schemes based on hash functions are described in: “A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack”, R. Cramer and V. Shoup, CRYPTO '98, pages 13-25, Springer-Verlag, 1998; and “Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack”, R. Cramer and V. Shoup, SIAM Journal on Computing, 33:167-226, 2001. A hash-free variant of the Cramer-Shoup encryption scheme is also described. In this hash-free scheme, the hashing is avoided by treating some part of the ciphertext (elements in a prime-order group) as a sequence of bits, chopping the sequence into blocks of bits, and treating the chopped values as numbers modulus the prime order which are then fed into a specific function evaluation. Essentially, this process builds a purpose-specific hash function which would allow proof of certain relations between the input and the output but require both the input and the output to be fully revealed. This of course defeats the object of proving relations between the input and the output because, if both are revealed, one could simply evaluate the appropriate function on the input and check the result against the given output. A linear Cramer-Shoup encryption scheme is also disclosed in “A Cramer-Shoup Encryption Scheme from the Linear Assumption and from Progressively Weaker Linear Variants, H. Shacham, 2007, Cryptology ePrint Archive, Report 2007/074. The security of this scheme is based on the Decisional Linear Assumption (DLIN) and relies crucially on the use of a hash function, again preventing proofs without revealing the ciphertext.
In the field of digital signatures, knowledge of a signature can be proved without revealing the signature to a verifier. Signature schemes permitting such proofs of knowledge can be implemented in a variety of ways. One example uses bilinear groups in implementing the signature scheme. This “structure-preserving” signature scheme is discussed in “Structure-Preserving Signatures and Commitments to Group Elements”, Abe et al., CRYPTO 2010, LNCS 6223, pp. 209-236, 2010.